package com.cdy.demo.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode131 {

	public static void main(String[] args) {
		Leetcode131 Leetcode5 = new Leetcode131();
	}


	List<List<String>> l = new ArrayList<>();

	public List<List<String>> partition(String s) {
		dfs(s, 0, s.length(), null);
		return l;
	}

	private void dfs(String s, int x,int y, List<String> strings){

		int len = y - x;
		if (len <= 0) {
			return;
		}
		if (len == 1) {
			strings.add(s.substring(x, y));
			return;
		}
		// 单独元素也算一个，所以不能从+1开始
		for (int i = x; i < len; i++) {
			if (s.charAt(x) == s.charAt(i)) {
				if (circle(s, x, i)) {
					strings.add(s.substring(x, i));
					if (x == 0) {
						strings = new ArrayList<>();
					}
					dfs(s, i+1, y, strings);
				}
			}
		}
		if (!strings.isEmpty()) {
			l.add(strings);
		}
	}

	private boolean circle(String s, int x, int y) {
		int len = y - x;
		for (int i = x; i < len; i++) {
			if (i > len - 1 - i || s.charAt(i) != s.charAt(len - 1 - i)) {
				return false;
			}
		}
		return true;
	}
}
